class Solution:
    """
    149. 直线上最多的点数
    https://leetcode-cn.com/problems/max-points-on-a-line/
    @date 2021年1月15日15:36:20
    @author mizzle rain
    """

    def maxPoints(self, points):
        n = len(points)
        if n == 0:
            return 0
        res = 1
        for i in range(0, n):
            verticals, duplicates = 1, 0
            dict1 = dict()
            for j in range(i+1, n):
                if points[j][0] == points[i][0]:
                    verticals += 1
                    if points[j][1] == points[i][1]:
                        duplicates += 1
            for j in range(i+1, n):
                if points[j][0] == points[i][0]:
                    continue
                # 防止浮点数精度丢失
                k = (points[j][1]-points[i][1]) *1000 / (points[j][0] - points[i][0]) * 1000
                dict1[k] = 2 if k not in dict1 else dict1[k] + 1
                res = max(res, dict1[k] + duplicates)
            res = max(res, verticals)
        return res


if __name__ == "__main__":
    s = Solution()
    res = s.maxPoints([[1, 1], [2, 1], [2, 2], [1, 4], [3, 3]])
    print(res)
